package com.algorithm;

/**
 * @author donye 反转链表的关键就是反转一个节点之后不能丢失后面节点的指针。 递归是从最后向前依次反转
 *         而用while循环则用临时变量来保存相关信息
 */
public class LinkReverseTester {
	
	public static class Node {
		// 直观起见，设置为public
		public int value;
		public Node next;

		public Node(int value, Node next) {
			this.value = value;
			this.next = next;
		}

		@Override
		public String toString() {
			if (next == null) {
				return "Node [value=" + value + "]";
			}
			return "Node [value=" + value + "]  " + next;
		}
	}

	public static Node reverseByRecursion(Node current) {
		// 处理基本情况，头结点为空时，或者递归到最后一个节点时
		if (current == null || current.next == null) {
			return current;
		}
		// 当不是基本情况时，递归处理当前操作中的节点的next节点，
		// 下面一行代码的目的是让当前节点的下一个节点在待会反转后，确保后续也已经反转。
		// 这个方法返回的永远都是反转后的头结点。
		Node headAfterReverse = reverseByRecursion(current.next);
		// 将当前节点的next节点反转，指向当前节点，即反转next节点。
		current.next.next = current;
		// 当前节点则不再指向next节点
		current.next = null;
		// 返回头结点
		return headAfterReverse;
	}

	public static Node reverseUsingTempNode(Node head) {
		// 将用三个临时变量指向最开始的三个节点
		Node p1 = head;
		Node p2 = head.next;
		Node p3 = head.next.next;
		// 将头结点设置为null
		p1.next = null;
		// p1,p2,p3开始循环依次向后面移动。
		// 每一次将p2所指向的节点反转后，3个变量就依次往后移动，直到p3==null
		while (p3 != null) {
			// 扭转p2
			p2.next = p1;
			// p1向后移动
			p1 = p2;
			// p2向后移动
			p2 = p3;
			// p3向后移动
			p3 = p3.next;
		}
		// 循环最后，p2节点指向最后一个节点，但还没有反转，所以最后还要反转一下
		p2.next = p1;
		// p2现在是头节点了
		return p2;
	}

	public static void main(String[] args) {
		// 构造一个链表
		Node e = new Node(5, null);
		Node d = new Node(4, e);
		Node c = new Node(3, d);
		Node b = new Node(2, c);
		Node a = new Node(1, b);
		System.out.println(a);
		Node headAfterReverse = reverseByRecursion(a);
		System.out.println(headAfterReverse);
		Node headAfterReverseAgain = reverseUsingTempNode(headAfterReverse);
		System.out.println(headAfterReverseAgain);
	}
}
